# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
root=TreeNode(5,None,None)
root.left=TreeNode(4,None,None)
root.left.left=TreeNode(11,None,None)
root.left.left.left=TreeNode(7,None,None)
root.left.left.right=TreeNode(2,None,None)
root.right=TreeNode(8,None,None)
root.right.left=TreeNode(13,None,None)
root.right.right=TreeNode(4,None,None)
root.right.right.right=TreeNode(1,None,None)


targetSum=22
def dfs(root,targetSum,curSum):
    if root.right==None and root.left==None:
        curSum += root.val
        if targetSum==curSum:
            return True  #找到了
        else:
            return False  #没找到
    rootLeft,rootRight=None,None
    if root.right!=None:
        rootRight=dfs(root.right,targetSum,curSum+root.val)
    if root.left!=None:
        rootLeft=dfs(root.left,targetSum,curSum+root.val)
    if rootLeft!=None and rootRight!=None:
        return (rootLeft or rootRight)
    if rootLeft==None and rootRight!=None:
        return rootRight
    if rootRight==None and rootLeft!=None:
        return rootLeft

def hasPathSum(root, targetSum):

    return dfs(root,targetSum,0)

print(hasPathSum(root,targetSum))
